package com.剑指offer.第一章;

/**
 * 输入数组 [0,1,2,3,4]   ==> [0,1,1,2,1]
 * <p>
 * 解放：让一个整数的二进制的右边有1 变成0，当全部变成0时，就结束。期间进行了多少的运算就是 有多个1
 * i&(i-1)
 */
public class 求n个整数的二进制1的个数 {

    public static int[] resolve1(int n) {
        int[] ints = new int[n];
//        int[] results = new int[n];
        for (int i = 0; i < n; i++) {
            int j = i;
            int result = 0;
            while (j != 0) {
                result += 1;
                j = j & (j - 1);
            }
            ints[i] = result;
        }
        return ints;
    }

    public static int[] resolve2(int n) {
        int[] ints = new int[n];
        for (int i = 1; i < n; i++) {
            ints[i] = ints[i & (i - 1)] + 1;
        }
        return ints;
    }

    public static int[] resolve3(int n) {
        int[] ints = new int[n];
        for (int i = 1; i < n; i++) {
            ints[i] = ints[i >> 1] + (i & 1);
        }
        return ints;
    }

    public static void main(String[] args) {
        for (int i : resolve3(5)) {
            System.out.println(i);
        }
    }

}
